home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-03 / huffman2.zip / HUFFMAN2.DOC < prev   
Text File  |  1992-05-29  |  4KB  |  146 lines
  1.                      HUFFMAN2.BAS and DECODER.BAS
  2.                         By Rich Geldreich 1992
  3.  
  4.  
  5.     The  two  QuickBASIC  4.5  programs  you  have  just  received can
  6. compress and decompress files with the  Huffman compression  algorithm.
  7. The first program HUFFMAN2.BAS,  takes an input file and compresses it
  8. to OUTPUT.HUF.   The second program, DECODER.BAS, takes OUTPUT.HUF and
  9. decompresses it a file specified  via  the  command  line.    The  two
  10. programs should be compiled for maximum speed.
  11.  
  12.     To compress EATME.DOC, use:
  13.  
  14. huffman2 eatme.doc
  15.  
  16.     To decompress the compressed file to EATME2.DOC, use:
  17.  
  18. decoder eatme2.doc
  19.  
  20.     Easy, right?
  21.  
  22.     I   have   released  these  two  programs  to  show  that  Huffman
  23. compression isn't really that hard to  implement.    What  is  Huffman
  24. compression?     It's  a  simple  compression  algorithm  which  takes
  25. advantage of a file's character distribution: if "A" is used more than
  26. "B",  for instance,  then  the  code representing "A" is significantly
  27. smaller than the code that represents "B".   It's not the best, but it
  28. isn't that bad.
  29.  
  30.     Lets say we want to compress the string "ABCDDBBAAAADD".    First,
  31. we must scan the string and tally up the count for each character:
  32.  
  33. A is used 5 times
  34. B is used 3 times
  35. C is used 1 time
  36. D is used 4 times
  37.  
  38.     Now that we have this distribution,  we must start making a binary
  39. tree that represents all of these characters; like this:
  40.  
  41. (* = not used)
  42.  
  43.  
  44.     5       3       1       4
  45.    / \     / \     / \     / \
  46.   A   *   B   *   C   *   D   *
  47.  
  48.  
  49.     Now we must start combining  "nodes"  until there is only one node
  50. at the top.   To do this we keep on combining 2 nodes which  have  the
  51. lowest frequency:
  52.  
  53.  
  54.     1 and 3 have the lowest frequency:
  55.  
  56.     5       4       4
  57.    / \     / \     / \
  58.   A   *   B   C   D   *
  59.  
  60.     4 and 4 have the lowest frequency:
  61.  
  62.     5        8
  63.    / \      / \
  64.   A   *    D   4
  65.               / \
  66.              B   C
  67.  
  68.     And finally, 5 and 8 have the lowest frequency:
  69.  
  70.          13
  71.         /  \
  72.        A    8
  73.            / \
  74.           D   4
  75.              / \
  76.             B   C
  77.  
  78.     To  represent  this  tree,   both programs use a linked list.   To
  79. represent each node,  the Father()  array  is used.   To represent the
  80. left and right arrows LeftSon() and RightSon() arrays are used.
  81.  
  82.     No that we have the combined tree,  we must travel down  the  tree
  83. and  find  out which bit sequence represents each character we wish to
  84. compress.  (A recursive procedure is used to do this.) We start at the
  85. top,  and every time we go  left  we  send  a "1" and every time we go
  86. right we send a "0".   So "A" will be represented with "1",  "B"  with
  87. "001",   "C" with "000",  & "D" with "01".   Notice that the character
  88. used most in the original string, "A", has the smallest code size, and
  89. the character used least, "C", has the biggest code size.
  90.  
  91.     A = 1       [used in 38% of the string]
  92.     B = 001     [used in 23%]
  93.     C = 000     [used in 7%]
  94.     D = 01      [used in 31%]
  95.  
  96.     "ABCDDBBAAAADD" will be compressed as:
  97.  
  98.     1 001 000 01 01 001 001 1 1 1 1 01 01
  99.  
  100.     or
  101.  
  102.     10010000 10100100 11111010 1
  103.  
  104.     ...so the original 13 character sequence has  been  compressed  to
  105. just 4 bytes.
  106.  
  107.     To decompress this 4  byte  sequence,   the  decoder must have the
  108. encoding tree handy(which must be send separately).
  109.  
  110.     The encoding tree was:
  111.  
  112.          13
  113.         /  \
  114.        A    8
  115.            / \
  116.           D   4
  117.              / \
  118.             B   C
  119.  
  120.     The output was:
  121.  
  122.     10010000 10100100 11111010 1
  123.  
  124.     Start  at the top.   The first bit is "1"- so go left.   The first
  125. character is then "A".  So far so good!  Now we go back to the top and
  126. start all over...
  127.  
  128.     The second bit is "0"- so go right. We're now at "8".
  129.     The third  bit is "0"- so go right again. We're now at "4".
  130.     The fourth bit is "1"- so go left.   We're now at "B".  "B" is the
  131. second character.
  132.  
  133.     Keep  on  repeating  this  until  all  of the characters have been
  134. decoded.
  135.  
  136.     That's  all!    Have  fun.   The two QB programs are in the public
  137. domain so do what you want  with  'em.    If you have any questions or
  138. cool ideas, I can be contacted at the following address:
  139.  
  140.     Rich Geldreich
  141.     410 Market St.
  142.     Gloucester City, NJ 08030
  143.     (609)-742-8752
  144.  
  145.  
  146.     May 29th, 1992